package com.lee.algorithm.sort.quick;

import static com.lee.algorithm.sort.SortUtil.print;
import static com.lee.algorithm.sort.SortUtil.swap;

/***
 * @description: 快排
 *      3个版本
 *      1、取最右侧元素作为划分值；只有小于区域
 *      2、取最右侧元素作为划分值；分两个区域：小于区域、大于区域（中间区域就是相等）
 *      3、随机取区域内的元素与最右侧元素交换，然后取最右侧元素作为划分值；分两个区域：小于区域、大于区域
 * @author : 青石路
 * @date: 2021/11/22 19:58
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] arr = new int[]{9,8,3,2,6,4,5,0,1,1,1};
        quickSort(arr);
        print(arr);
    }

    /**
     *
     * @param arr
     */
    public static void quickSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        quickSort(arr, 0, arr.length-1);
    }

    /**
     * partition版本
     * @param arr
     * @param left
     * @param right
     * @author 博客园 @ 青石路
     */
    private static void quickSort(int[] arr, int left, int right) {
        
        if (left < right) {

            /**
             * 将 left 至 right 之间的随机位置上的一个数与 arr[right] 进行交换
             * 那么 arr[right] 即是 arr[left] ~ arr[right] 之间的随机某个数
             * 交换完之后，以 arr[right] 作为 target，进行荷兰国旗问题处理
             */
            swap(arr, left + (int) (Math.random() * (right-left+1)), right);

            int[] p = partition(arr, left, right);

            // 递归处理小于区
            quickSort(arr, left, p[0]);

            // 递归处理大于区
            quickSort(arr, p[1]+1, right);
        }
    }

    /**
     * 处理arr[left...right]
     * 默认以 arr[right] 做划分（arr[right]作为划分值，也就是枢纽值）
     * 返回等于区域（左边界、右边界），所以返回一个长度为2的数组
     * （荷兰国旗问题）
     *      1) [i] < 划分值，[i]和 <区 下一个交换，<区右扩，i++
     *      2) [i] = 划分值，i++
     *      3) [i] > 划分值,[i]和 >区 前一个交换， >区左扩，i不变
     * @param arr
     * @param left
     * @param right
     * @author 博客园 @ 青石路
     * @return
     */
    private static int[] partition(int[] arr, int left, int right) {

        // less、more 分别是两个边界下标， less => 小于区右边界，more => 大于区左边界
        int less = left - 1;
        int more = right;

        // left => 遍历的元素下标
        while (left < more) {
            if (arr[left] < arr[right]) {
                // 当前数 < 划分值 当前数 和 小于区下一个数交换，小于区右扩
                // ++less => 小于区下一个数，小于区右扩
                swap(arr, ++less, left++);
            } else if (arr[left] > arr[right]) {
                // 当前数 > 划分值，当前数和 大于区前一个数交换，大于区左扩
                // --more => 大于区前一个数，大于区左扩
                swap(arr, --more, left);
            } else {
                left ++;
            }
        }

        // 将枢纽值置于中间，左边 <= 枢纽值 < 右边
        swap(arr, more, right);

        // less+1 ~ left 区域内都等于枢纽值

        return new int[]{less, more};
    }
}
